package com.shuang.tree26;

public class IsBalanced {

    //递归法 求高度 用后序遍历  左右子树高度差大于1 则不是平衡二叉树
    //定义函数 判断左右高度差是否大于1 大于一不是平衡二叉树 返回-1 小于等于 1 返回高度具体的值
    public boolean isBalanced(TreeNode root) {
        return getHeight(root) != -1;
    }

    public int getHeight(TreeNode root) {

        //终止条件
        if (root == null) {
            return 0;
        }

        //左
        int leftHeight = getHeight(root.left);
        if (leftHeight == -1) {
            return -1;
        }

        //右
        int rightHeight = getHeight(root.right);
        if (rightHeight == -1) {
            return -1;
        }

        // 左右子树高度差大于1，return -1表示已经不是平衡树了
        if (Math.abs(leftHeight - rightHeight) > 1) {
            return -1;
        }

        //中
        int res = Math.max(leftHeight, rightHeight) + 1;

        return res;

    }
}
